#define _CRT_SECURE_NO_WARNINGS 1

#include<iostream>
#include<vector>
#include<queue>

using namespace std;

int dx[8] = { 0,0,-1,1,1,-1,-1,1 };
int dy[8] = { 1,-1,0,0,1,1,-1,-1 };

bool dfs(int sx, int sy, int fx, int fy, int t)
{
    if (t <= 0)
    {
        return sx == fx && sy == fy;
    }

    for (int i = 0; i < 8; i++)
    {
        int x = dx[i] + sx;
        int y = dy[i] + sy;
        bool flag = dfs(x, y, fx, fy, t - 1);
        if (flag)
            return true;
    }
    return false;
}

bool __isReachableAtTime(int sx, int sy, int fx, int fy, int t) {
    return dfs(sx, sy, fx, fy, t);
}

void ymove(int& disx, int& disy, int count)
{
    if (disy > 0)
    {
        disx = disx + count;
        disy--;
    }
    else if (disy < 0)
    {
        disx = disx + count;
        disy++;
    }
    else
        disx = disx + count;
}

bool _isReachableAtTime(int sx, int sy, int fx, int fy, int t) {
    int disx = fx - sx;
    int disy = fy - sy;
    if (disx == 0 && disy == 0 && t % 2 == 1)
        return false;
    while (t--)
    {
        if (disx > 0)
        {
            ymove(disx, disy, -1);
        }
        else if (disx < 0)
        {
            ymove(disx, disy, 1);
        }
        else if(disx == 0)
            ymove(disx, disy, 0);
    }
    return disx == 0 && disy == 0;
}

bool isReachableAtTime(int sx, int sy, int fx, int fy, int t) {
    if (sx == fx && sy == fy && t == 1)
        return false;
    int c = abs(fx - sx);
    int r = abs(fy - sy);

    int res = max(c, r);
    if (t >= res)
        return true;
    else
        return false;
}

typedef pair<int, int> PII;
int minimumMoves(vector<vector<int>>& grid) {
    bool sta[3][3];
    memset(sta, false, sizeof(sta));
    queue<PII> q;
    for (int i = 0; i < grid.size(); i++)
    {
        for (int j = 0; j < grid[0].size(); j++)
        {
            if (grid[i][j] != 0)
                sta[i][j] = true;
            else
                q.push(make_pair(i, j));
        }
    }

    int res = 0;
    for (int i = 0; i < grid.size(); i++)
    {
        for (int j = 0; j < grid[0].size(); j++)
        {
            while (grid[i][j] > 1)
            {
                int Max = INT_MAX;
                int rx, ry;
                int n = q.size();
                for (int a = 0; a < n; a++)
                {
                    PII top = q.front();
                    q.pop();
                    int x = top.first, y = top.second;
                    if (sta[x][y] == false)
                    {
                        int count = abs(i - x) + abs(j - y);
                        if (count < Max)
                        {
                            rx = x, ry = y;
                            Max = count;
                        }
                        q.push(make_pair(x, y));
                    }
                }
                res += Max;
                sta[rx][ry] = true;
                grid[i][j] --;
            }
        }
    }
    return res;
}

bool isMatch(string s, string p) {
    int n = s.size();
    int m = p.size();

    auto match = [&](int i, int j)
    {
        if (i == 0)
            return false;
        if (p[j - 1] == '.')
            return true;
        return s[i - 1] == p[j - 1];
    };

    vector<vector<int>> dp(n + 1, vector<int>(m + 1));
    dp[0][0] = true;
    for (int i = 0; i <= n; i++)
    {
        for (int j = 1; j <= m; j++)
        {
            if (p[j - 1] == '*')
            {
                dp[i][j] |= dp[i][j - 2];
                if (match(i, j - 1))
                {
                    dp[i][j] |= dp[i - 1][j];
                }
            }

            else
            {
                if (match(i, j))
                {
                    dp[i][j] |= dp[i - 1][j - 1];
                }
            }
        }
    }
    return dp[n][m];
}

int main()
{
    string s = "aa";
    string p = "a*";
    isMatch(s, p);
    /*vector<vector<int>> vv = { {1,2,2},{1,1,0},{0,1,1} };
    cout << minimumMoves(vv);*/
    //cout << isReachableAtTime(1, 2, 1, 2, 1);
	return 0;
}




